所有长度为 \(1\) 的子数组，包含的元素必定是众数，所以只需判断 \(k\) 是否存在于数组中。
1
2
3
4
5
6
7
8
9
10
| public static void solve() {
int n = io.nextInt(), k = io.nextInt();
boolean ok = false;
for (int i = 0; i < n; i++) {
if (k == io.nextInt()) {
ok = true;
}
}
io.println(ok ? "YES" : "NO");
}
|
两个奇数相加得到偶数，两个奇数相乘得到奇数，奇数不会被偶数整除，所以构造一个全是奇数的序列即可。
1
2
3
4
5
6
7
| public static void solve() {
int n = io.nextInt();
for (int i = 0; i < n; i++) {
io.print(i * 2 + 1 + " ");
}
io.println();
}
|
只要 \(x\) 在最小值和最大值之间，就总是可以被表示出来。
1
2
3
4
5
6
7
8
| public static void solve() {
int n = io.nextInt(), k = io.nextInt();
long x = io.nextLong();
long a = (long) (1 + k) * k / 2;
long b = (long) (n - k + 1 + n) * k / 2;
if (x >= a && x <= b) io.println("YES");
else io.println("NO");
}
|
数组被 \(l\) 和 \(r\) 分段，每一段都是相互独立的，可以单独考虑段内的反转情况。可以发现段内反转总是中心对称的，每个元素是否反转，取决于该元素位置被反转次数的奇偶性，可以用两边向中间求累加和的方式统计，也可以用差分数组。（比赛时我没有统计奇偶性，而是抵消相邻的反转的相同部分）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| public static void solve() {
int n = io.nextInt(), k = io.nextInt();
char[] s = io.next().toCharArray();
int[] l = new int[k];
for (int i = 0; i < k; i++) {
l[i] = io.nextInt() - 1;
}
int[] r = new int[k];
for (int i = 0; i < k; i++) {
r[i] = io.nextInt() - 1;
}
int q = io.nextInt();
int[] cnt = new int[n];
for (int i = 0; i < q; i++) {
cnt[io.nextInt() - 1]++;
}
for (int i = 0; i < k; i++) {
int sum = 0;
for (int a = l[i]; a <= (l[i] + r[i]) / 2; a++) {
int b = r[i] + l[i] - a;
sum += cnt[a] + cnt[b];
if (sum % 2 == 1) {
char c = s[a];
s[a] = s[b];
s[b] = c;
}
}
}
io.println(new String(s));
}
|
比较简单的做法是，计算每个比特位的前缀和，然后对每个查询二分答案的位置，将二分位置的值和 \(k\) 比较来判断二分的走向。比赛时我是用下面的方法做的，就是没想到二分，其实也可以不用二分，但是没看明白为什么，代码在此。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| public static void solve() {
int n = io.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = io.nextInt();
}
int[][] next = new int[n + 1][32];
Arrays.fill(next[n], n);
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j < 32; j++) {
next[i][j] = next[i + 1][j];
if ((a[i] >> j & 1) == 0) {
next[i][j] = i;
}
}
}
int q = io.nextInt();
while (q-- != 0) {
int l = io.nextInt() - 1, k = io.nextInt();
if (a[l] < k) {
io.print("-1 ");
continue;
}
int lo = l, hi = n - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
int cur = 0;
for (int i = 0; i < 32; i++) {
if (next[mid][i] > mid && next[mid][i] == next[l][i]) {
cur |= 1 << i;
}
}
if (cur >= k) lo = mid + 1;
else hi = mid - 1;
}
io.print(hi + 1 + " ");
}
io.println();
}
|